Search for: All records

This paper is a survey of results and problems related to the following question: is it true that if G is a tournament with sufficiently large chromatic number, then G has two vertex-disjoint subtournaments A,B, both with large chromatic number, such that all edges between them are directed from A to B? We describe what we know about this question, and report some progress on several other related questions, on tournament colouring and domination. 

Menger's well-known theorem from 1927 characterizes when it is possible to find k vertex-disjoint paths between two sets of vertices in a graph G. Recently, Georgakopoulos and Papasoglu and, independently, Albrechtsen, Huynh, Jacobs, Knappe and Wollan conjectured a coarse analogue of Menger's theorem, when the k paths are required to be pairwise at some distance at least d. The result is known for k ≤ 2, but we will show that it is false for all k ≥ 3, even if G is constrained to have maximum degree at most three. We also give a simpler proof of the result when k = 2. 

How are Reddit communities responding to AI-generated content? We explored this question through a large-scale analysis of subreddit community rules and their change over time. We collected the metadata and community rules for over 300,000 public subreddits and measured the prevalence of rules governing AI. We labeled subreddits and AI rules according to existing taxonomies from the HCI literature and a new taxonomy we developed specific to AI rules. While rules about AI are still relatively uncommon, the number of subreddits with these rules more than doubled over the course of a year. AI rules are more common in larger subreddits and communities focused on art or celebrity topics, and less common in those focused on social support. These rules often focus on AI images and evoke, as justification, concerns about quality and authenticity. Overall, our findings illustrate the emergence of varied concerns about AI, in different community contexts. Platform designers and HCI researchers should heed these concerns if they hope to encourage community self-determination in the age of generative AI. We make our datasets public to enable future large-scale studies of community self-governance. 

Deep learning-based prediction models for High-Level Synthesis (HLS) of hardware designs often struggle to generalize. In this paper, we study how to close the generalizability gap of these models through pretraining on synthetic data and introduce Iceberg, a synthetic data augmentation approach that expands both large language model (LLM)-generated programs and weak labels of unseen design configurations. Our weak label generation method is integrated with an in-context model architecture, enabling meta-learning from actual and proximate labels. Iceberg improves the geometric mean modeling accuracy by 86.4% when adapt to six real-world applications with few-shot examples and achieves a 2.47× and a 1.12× better offline DSE performance when adapting to two different test datasets. Our open-sourced code is here: https://github.com/UCLA-VAST/iceberg. 

Abstract Many reaction networks arising in applications are multistationary, that is, they have the capacity for more than one steady state, while some networks exhibit absolute concentration robustness (ACR), which means that some species concentration is the same at all steady states. Both multistationarity and ACR are significant in biological settings, but only recently has attention focused on the possibility for these properties to coexist. Our main result states that such coexistence in at-most-bimolecular networks (which encompass most networks arising in biology) requires at least three species, five complexes and three reactions. We prove additional bounds on the number of reactions for general networks based on the number of linear conservation laws. Finally, we prove that, outside of a few exceptional cases, ACR is equivalent to non-multistationarity for bimolecular networks that are small (more precisely, one-dimensional or up to two species). Our proofs involve analyses of systems of sparse polynomials, and we also use classical results from chemical reaction network theory.